
/**
 * A星寻路
 * @author chenkai
 * @since 2017/11/3
 */
namespace astar{
	export class AStar
	{
		private _open:Array<any>;               //待考察表
		private _closed:Array<any>;             //已考察表
		private _grid:astar.Grid;               //网格
		private _endNode:Node;                  //终点Node
		private _startNode:Node;                //起点Node
		private _path:Array<any>;               //保存路径
		private _heuristic:Function;            //寻路算法
		private _straightCost:number = 1.0;     //上下左右走的代价
		private _diagCost:number = Math.SQRT2;  //斜着走的代价 
		
		
		public constructor()
		{	
			//this._heuristic = this.manhattan;  
			//this._heuristic = this.euclidian;
			this._heuristic = this.diagonal;
		}
		
		//寻路
		public findPath(grid:Grid):boolean
		{
			this._grid = grid;
			this._open = [];
			this._closed = [];
			
			this._startNode = this._grid.startNode;
			this._endNode = this._grid.endNode;
			
			this._startNode.g = 0;
			this._startNode.h = this._heuristic(this._startNode);
			this._startNode.f = this._startNode.g + this._startNode.h;
			
			return this.search();
		}
		
		//查找路径
		public search():boolean
		{
			var node:Node = this._startNode;
			while(node != this._endNode)
			{
				var startX = Math.max(0, node.x - 1);
				var endX = Math.min(this._grid.numCols - 1, node.x + 1);
				var startY = Math.max(0, node.y - 1);
				var endY = Math.min(this._grid.numRows - 1, node.y + 1);
				
				for(var i = startX; i <= endX; i++)
				{
					for(var j = startY; j <= endY; j++)
					{	
						//不让斜着走
						// if(i != node.x && j != node.y){
						// 	continue;
						// }

						var test:Node = this._grid.getNode(i, j);
						if(test == node || 
							!test.walkable ||
							!this._grid.getNode(node.x, test.y).walkable ||
							!this._grid.getNode(test.x, node.y).walkable)
						{
							continue;
						}
						
						var cost:number = this._straightCost;
						if(!((node.x == test.x) || (node.y == test.y)))
						{
							cost = this._diagCost;
						}
						var g = node.g + cost * test.costMultiplier;
						var h = this._heuristic(test);
						var f = g + h;
						if(this.isOpen(test) || this.isClosed(test))
						{
							if(test.f > f)
							{
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}
						else
						{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							this._open.push(test);
						}
					}
				}
				for(var o = 0; o < this._open.length; o++)
				{
				}
				this._closed.push(node);
				if(this._open.length == 0)
				{
					console.log("AStar >> no path found"+this._endNode);
					return false
				}
				
				let openLen = this._open.length;
				for(let m=0;m<openLen;m++){
					for(let n=m+1;n<openLen;n++){
						if(this._open[m].f > this._open[n].f){
							let temp = this._open[m];
							this._open[m] = this._open[n];
							this._open[n] = temp;
						}
					}
				}

				node = this._open.shift() as Node;
			}
			this.buildPath();
			return true;
		}
		
		//获取路径
		private buildPath():void
		{
			this._path = new Array();
			var node:Node = this._endNode;
			this._path.push(node);
			while(node != this._startNode)
			{
				node = node.parent;
				this._path.unshift(node);
			}
		}
		
		public get path()
		{
			return this._path;
		}
		
		//是否待检查
		private isOpen(node:Node):boolean
		{
			for(var i = 0; i < this._open.length; i++)
			{
				if(this._open[i] == node)
				{
					return true;
				}
			}
			return false;
		}
		
		//是否已检查
		private isClosed(node:Node):boolean
		{
			for(var i = 0; i < this._closed.length; i++)
			{
				if(this._closed[i] == node)
				{
					return true;
				}
			}
			return false;
		}
		
		//曼哈顿算法
		private manhattan(node:Node)
		{
			return Math.abs(node.x - this._endNode.x) * this._straightCost + Math.abs(node.y + this._endNode.y) * this._straightCost;
		}
		

		private euclidian(node:Node)
		{
			var dx = node.x - this._endNode.x;
			var dy = node.y - this._endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * this._straightCost;
		}
		
		private diagonal(node:Node)
		{
			var dx = Math.abs(node.x - this._endNode.x);
			var dy = Math.abs(node.y - this._endNode.y);
			var diag = Math.min(dx, dy);
			var straight = dx + dy;
			return this._diagCost * diag + this._straightCost * (straight - 2 * diag);
		}
		
		public get visited()
		{
			return this._closed.concat(this._open);
		}
	}

}